Mit Hilfe der Informatik wird an Problemen gearbeitet, die schnelle Berechnungen, das Rechen mit großen Datenmengen und Zahlen und komplexen Verfahren beinhalten.

Informatik steckt in vielen Lebensbereichen. Wir sind umgeben von Geräten und Produkten, die nur durch die Informatik erschaffen werden konnten.

Aber auch die Informatik hat ihre Grenzen. Probleme wie zum Beispiel das Hexenpuzzle sind ab einer bestimmten Größe nicht mehr berechenbar.
Grenzen auszuloten ist auch Teil der Informatik.

Was ist das Hexenpuzzle?

Das Hexenpuzzle ist ein Spiel, welches aus quadratischen Kartenteilen besteht. Das Ziel des Spiels ist es, alle Karten "richtig" anzuordnen. Das heißt die Karten sind so zu legen, dass alle Hexen die gleiche Farbe am Kopf sowie am Körper haben.

Warum ist es schwierig?

Die Anzahl an möglichen Kombinationen steigt sehr schnell an, wenn die Anzahl an Karten erhöht wird. Bei einem 2 x 2 Puzzle gibt es 6144 mögliche Kombinationen. Bei einem 5 x 5 Puzzle gibt es bereits 1.75 e+40 Kombinationen.
Um zu berechnen, wieviele mögliche Kombinationen es gibt, kann für ein n x n Puzzle mit N Karten wie folgt vorgegangen werden: Für das erste Feld gibt es N verschiedene Möglichkeiten. Für das zweite Feld gibt es noch N-1 viele Möglichkeiten, für das dritte Feld N-2 und so weiter. Zusätzlich kann jede Karte noch in vier verschiedene Richtungen gedreht werden. Daraus ergibt sich als Formel für die Anzahl der Kombinationen: N! x 4^N.

Wie geht der Mensch vor?

Das menschliche Gehirn erfasst sofort unterschiedliche Ansatzpunkte für Lösungen, trifft Vorentscheidungen und legt Kriterien für passende Kombinationen fest. Doch schon beim 6 x 6-Puzzle versagt diese Gabe, sich einen Überblick zu verschaffen. Auch der Mensch muss nun systematisch ausprobieren.

Wie geht der Computer vor?

Der Computer geht an diese Aufgabe heran, indem er systematisch eine Kombination nach der anderen ausprobiert. Seine schnelle Arbeitsgeschwindigkeit ist der des Menschen überlegen: 200 Mio. Puzzleteile pro Sekunde! Doch das sture Ausprobieren jeder erdenklichen Kombination kann bei bestimmten Aufgaben den Computer in die Knie zwingen.

Wie geht der Informatiker vor?

Informatiker überlegen vorab, ob eine Aufgabe den Rechner überfordern könnte und entwickeln alternative Lösungen. Aufgaben wie dem Hexenpuzzle kann man auch mit der Rechengeschwindigkeit nicht beikommen. Viele Lösungsansätze in der Informatik „skalieren“ nicht. Wenn sich eine Aufgabenstellung verdoppelt, reicht es nicht automatisch, den Arbeitsaufwand zu verdoppeln. Meist bedarf es eines ungleich höheren Einsatzes. Ähnliches gilt z. B. für das Sortieren von Karteikarten oder für die Streckenauswahl eines Routenplaners. Beim Hexenpuzzle bietet sich als Alternative, die Aufgabe geringfügig abzuändern und zwei falsche Kombinationen zuzulassen. Dann würde der Computer eine Annäherungslösung schaffen.